#include <atomic>
#include <cassert>
#include "iqueue.h"

using std::atomic;
using std::memory_order_relaxed;

template <class T>
class LFQueue : public IQueue<T>{
	public:

	LFQueue();
	~LFQueue();
	
	void Enqueue(const T& elem);
	bool Dequeue(T *presult);

	private:

	struct Item {
		Item(): pnext_(nullptr) {}
		Item(Item *pnext, const T& data): pnext_(pnext), data_(data) {}
		atomic<Item*> pnext_;
		T data_;
	};

	atomic<Item*> phead_;
	atomic<Item*> ptail_;
};

template <class T>
LFQueue<T>::LFQueue():
	phead_(nullptr),
	ptail_(nullptr) {
	
	Item* new_item = new Item;
	phead_.store(new_item);
	ptail_.store(new_item);
	
}

template <class T>
LFQueue<T>::~LFQueue() {
	Item *pnew_item = phead_.load();
	while (pnew_item) {
		Item *tmp = pnew_item;
		pnew_item = pnew_item->pnext_.load();
		delete tmp;
	}
}

template <class T>
void LFQueue<T>::Enqueue(const T& elem) {
	Item *pnew_item = new Item(nullptr, elem);
	Item *ptail_copy = nullptr;
	bool succ = true;
	do {
		Item *nul = nullptr;
		ptail_copy = ptail_.load(memory_order_relaxed);
		if (!ptail_copy)
			continue;
		assert(ptail_copy);
		succ = ptail_copy->pnext_.compare_exchange_strong(nul, pnew_item,
		    memory_order_relaxed, memory_order_relaxed);
		if (!succ) {
			ptail_.compare_exchange_strong(ptail_copy,
			    ptail_copy->pnext_.load(memory_order_relaxed),
			    memory_order_relaxed, memory_order_relaxed);
		}
	} while (!succ);
	ptail_.compare_exchange_strong(ptail_copy, pnew_item,
	    memory_order_relaxed, memory_order_relaxed);
}

template <class T>
bool LFQueue<T>::Dequeue(T *presult) {
	assert(presult);

	Item *phead_copy = nullptr, *pnext = nullptr;
	do {
		phead_copy = phead_.load(memory_order_relaxed);
		assert(phead_copy);
		pnext = phead_copy->pnext_.load(memory_order_relaxed);
		if (!pnext)
			return false;
	} while (!phead_.compare_exchange_weak(phead_copy, pnext,
	    memory_order_relaxed, memory_order_relaxed));
	*presult = pnext->data_;
	delete phead_copy;
	return true;
}

